home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
ftp.mactech.com 2010
/
ftp.mactech.com.tar
/
ftp.mactech.com
/
machack
/
Hacks97
/
WarriorsProgress.sit
/
Warrior’s Progress
/
source code
/
Source
/
Libraries
/
Trees
/
RedBlackTree.cp
< prev
next >
Wrap
Text File
|
1997-06-28
|
5KB
|
231 lines
// RedBlackTree.cp
#ifndef RedBlackTree_h
#include "RedBlackTree.h"
#endif
#ifndef RedBlackNode_h
#include "RedBlackNode.h"
#endif
RedBlackTree::RedBlackTree()
: blackHeight( 0 )
{
}
RedBlackTree::~RedBlackTree()
{
Assert( blackHeight == 0 );
}
RedBlackNode *RedBlackTree::DownCast( TreeNode *n )
{
return static_cast< RedBlackNode* >( n );
}
const RedBlackNode *RedBlackTree::DownCast( const TreeNode *n )
{
return static_cast< const RedBlackNode* >( n );
}
void RedBlackTree::Add( RedBlackNode& newNode, AtRoot )
{
Assert( newNode.IsRed() );
Tree::Add( newNode, atRoot );
Assert( blackHeight == 0 );
}
void RedBlackTree::Add( RedBlackNode& newNode,
Before,
RedBlackNode& next )
{
Assert( newNode.IsRed() );
Assert( !next.HasLeftChild() );
Assert( next.IsBlack() || !next.HasRightChild() );
Assert( !next.HasRightChild() || next.Right()->IsRed() );
Assert( !next.HasRightChild() || next.Right()->IsLeaf() );
Tree::Add( newNode, before, next );
FixRedChain( newNode );
}
void RedBlackTree::Add( RedBlackNode& newNode,
After,
RedBlackNode& previous )
{
Assert( newNode.IsRed() );
Assert( !previous.HasRightChild() );
Assert( previous.IsBlack() || previous.IsLeaf() );
Assert( !previous.HasLeftChild() || previous.Left()->IsRed() );
Assert( !previous.HasLeftChild() || previous.Left()->IsLeaf() );
Tree::Add( newNode, after, previous );
FixRedChain( newNode );
}
void RedBlackTree::Remove( RedBlackNode& toRemove )
{
if ( toRemove.HasLeftChild() )
{
RedBlackNode *previous = toRemove.Previous();
Assert( previous != 0 );
toRemove.SwapWith( *previous );
if ( toRemove.HasLeftChild() )
{
Assert( toRemove.Left()->IsRed() );
toRemove.Left()->RotateUp();
}
}
else if ( toRemove.HasRightChild() )
{
RedBlackNode *next = toRemove.Next();
Assert( next != 0 );
toRemove.SwapWith( *next );
if ( toRemove.HasRightChild() )
{
Assert( toRemove.Right()->IsRed() );
toRemove.Right()->RotateUp();
}
}
Assert( toRemove.IsLeaf() );
Redden( toRemove );
Tree::Remove( toRemove );
}
void RedBlackTree::RemoveAll()
{
RedBlackNode *first = First();
while ( first != 0 )
{
Assert( !first->HasLeftChild() );
if ( first->HasRightChild() )
Remove( *first->Right() );
Assert( !first->HasRightChild() );
RedBlackNode *next = first->Parent();
Remove( *first );
first = next;
}
}
void RedBlackTree::FixRedChain( RedBlackNode& toFix )
{
Assert( &toFix.Owner() == this );
RedBlackNode *lower = &toFix;
while ( true )
{
Assert( lower != 0 );
Assert( lower->IsRed() );
RedBlackNode *upper = lower->Parent();
if ( upper == 0 || upper->IsBlack() )
break;
if ( upper->IsRoot() )
{
upper->red = false;
blackHeight++;
break;
}
RedBlackNode *sibling = upper->Sibling();
if ( sibling == 0 || sibling->IsBlack() )
{
if ( lower->IsLeftChild() != upper->IsLeftChild() )
{
lower->RotateUp();
lower->RotateUp();
}
else
upper->RotateUp();
break;
}
lower = upper->Parent();
lower->Raise();
}
}
void RedBlackTree::Redden( RedBlackNode& toRedden )
{
Assert( &toRedden.Owner() == this );
Assert( toRedden.RedChildren() == 0 );
if ( toRedden.IsRed() )
return;
// Try changing the root color
{
if ( toRedden.IsRoot() )
{
Assert( blackHeight > 0 );
toRedden.red = true;
blackHeight--;
return;
}
}
RedBlackNode *sibling = toRedden.Sibling();
Assert( sibling != 0 );
if ( sibling->IsRed() )
{
sibling->RotateUp();
sibling = toRedden.Sibling();
Assert( sibling != 0 );
}
Assert( !sibling->IsRed() );
// If we have a red left niece, borrow from our sibling
{
RedBlackNode *leftNiece = sibling->Left();
if ( leftNiece != 0 && leftNiece->IsRed() )
{
if ( sibling->IsLeftChild() )
sibling->RotateUp();
else
{
leftNiece->RotateUp();
leftNiece->RotateUp();
}
Assert( toRedden.IsRed() );
return;
}
}
// If we have a red right niece, borrow from our sibling
{
RedBlackNode *rightNiece = sibling->Right();
if ( rightNiece != 0 && rightNiece->IsRed() )
{
if ( sibling->IsRightChild() )
sibling->RotateUp();
else
{
rightNiece->RotateUp();
rightNiece->RotateUp();
}
Assert( toRedden.IsRed() );
return;
}
}
Redden( *toRedden.Parent() );
toRedden.Parent()->Lower();
}
bool RedBlackTree::Valid() const
{
if ( IsEmpty() )
return blackHeight == 0;
return Root()->Valid( blackHeight );
}